#include <stdio.h>
#include <stdlib.h>
#include <time.h>


//The K value 
//#define N_QUEENS 16
#define N_ITERATIONS 100000

int queens_columns[N_QUEENS];

void makeRandomInitBoard(void) {
	int i;
	for (i = 0; i < N_QUEENS; i++){
		queens_columns[i] = rand() % N_QUEENS;
	}
}

//Returns the total number of collisions on the board
int get_number_of_collisions(void){
	int queen;
	int collisions = 0;

	for(queen = 0; queen < N_QUEENS; queen++){
		int other_queen;
		for(other_queen = 0; other_queen < N_QUEENS; other_queen++){
			if (other_queen == queen){
				continue;
			}
			if(queens_columns[other_queen] == queens_columns[queen]){
				collisions++;
			}
			else if(queens_columns[other_queen] == (queens_columns[queen] + abs(queen - other_queen))){
				collisions++;
			}
			else if(queens_columns[other_queen] == (queens_columns[queen] - abs(queen - other_queen))){
				collisions++;
			}
		}
	}
	return collisions;
}

//Function that returns the column that gives the column with the fewest collisions for a given queen.
int min_conflicts_for_a_queen(int queen) {
	int column;
	int best_column;
	int collisions_in_best_column = N_QUEENS+1;
	for(column = 0; column < N_QUEENS; column++){
		int collisions = 0;
		int other_queen;
		for(other_queen = 0; other_queen < N_QUEENS; other_queen++){
			if (other_queen == queen){
				continue;
			}
			if(queens_columns[other_queen] == column){
				collisions++;
			}
			else if(queens_columns[other_queen] == (column + abs(queen - other_queen))){
				collisions++;
			}
			else if(queens_columns[other_queen] == (column - abs(queen - other_queen))){
				collisions++;
			}
		}
		if(collisions < collisions_in_best_column){
			best_column = column;
			collisions_in_best_column = collisions;
		}
		//If the new column is as good as the old we have a 50 % chance of using it
		else if(collisions == collisions_in_best_column && rand()%10 < 5){
			best_column = column;
		}
	}

	return best_column;
}

void printBoard(void){
	int i,j;
	for(i = 0; i < N_QUEENS; i++){
		for(j = 0; j < N_QUEENS; j++){
			printf("|");
			if(queens_columns[i] == j){
				printf("X");
			}else{
				printf(" ");
			}
		}
		printf("|\n");
	}
}

int main(int argc, char **argv) {
	srand ( time(NULL) );

	makeRandomInitBoard();

	int success = 0;

	int i;
	for(i = 0; i < N_ITERATIONS; i++){
		
		//Check if correct solution
		
		int collisions = get_number_of_collisions();
		if (collisions == 0){
			success = 1;
			break;
		}

		//Choose a random  queen
		int current_queen = rand() % N_QUEENS;
		
		//Find the best column for the queen
		int best_column = min_conflicts_for_a_queen(current_queen);
		
		//Print stuff
		printf("Iteration: %d\t Number of conflicts: %d\n",i,collisions);
		//printf("Queen %d will be moved to %d\n", current_queen, best_column);

		//Put the queen in the optimal column
		queens_columns[current_queen] = best_column;

		//printBoard();
		
	}

	//Print result
	if(success){
		printf("Hurray!!!\n");
		printf("Solution found after %d interations\n", i);
		printBoard();
	}
	else{
		printf("Booo... No solution was found, even after %d iterations\n", N_ITERATIONS);
	}




	return 0;
}
